//https://leetcode.cn/problems/regular-expression-matching/description/
//匹配正则表达式
//给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
//'.' 匹配任意单个字符
//'*' 匹配零个或多个前面的那一个元素
//所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
bool isMatch(char* s, char* p) {
    int lens = strlen(s);
    int lenp = strlen(p);

    bool dp[lens + 1][lenp + 1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;

    for(int j = 2; j < lenp + 1; j++)
    {
        if(p[j - 1] == '*')
        {
            dp[0][j] = dp[0][j - 2];//前面那个字符匹配零个
        }
    }

    for(int i = 1; i < lens + 1; i++)
    {
        for(int j = 1; j < lenp + 1; j++)
        {
            if(s[i - 1] == p[j - 1]||p[j - 1] == '.')//新字符刚好匹配
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if(p[j - 1] == '*')
            dp[i][j] = dp[i][j - 2]||(dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
        }
    }

    return dp[lens][lenp];
}